package Acm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;

public class AClosestCities {
    static int[][] dp1;
    static int[][] dp2;
    public static int dfs1(int src,int dest,int[] citys){
        if(src == dest){
            return 0;
        }
        if(dp1[src][dest]!= 0){
            return dp1[src][dest];
        }
        if(src<dest){
            if(src == 1){
                dp1[src][dest]=dfs1(src+1,dest,citys)+1;
            }else{
                if(citys[src-1]-citys[src-2]>citys[src]-citys[src-1]){
                    dp1[src][dest]=dfs1(src+1,dest,citys)+1;
                }else{
                    dp1[src][dest]=citys[src]-citys[src-1]+dfs1(src+1,dest,citys);
                }
            }
        }else{
            if(src == citys.length){
                dp1[src][dest]=dfs1(src-1,dest,citys)+1;
            }else{
                if(citys[src-1]-citys[src-2]<citys[src]-citys[src-1]){
                    dp1[src][dest]=dfs1(src-1,dest,citys)+1;
                }else{
                    dp1[src][dest]=citys[src-1]-citys[src-2]+dfs1(src-1,dest,citys);
                }
            }
        }

        return dp1[src][dest];
    }
    public static void main(String[] args) throws IOException {

        StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int n1 =(int)st.nval;
        for (int i = 0; i < n1; i++) {
            dp1=new int[3001][3001];
            st.nextToken();
            int len = (int)st.nval;
            int[] citys = new int[len];
            for (int l = 0; l < len; l++) {
                st.nextToken();
                citys[l] = (int)st.nval;
            }
            st.nextToken();
            int n2 =  (int)st.nval;
            for (int j = 0; j < n2; j++) {
                st.nextToken();
                int src= (int)st.nval;
                st.nextToken();
                int dest= (int)st.nval;
                System.out.println(dfs1(src,dest,citys));
            }
        }
    }
}
